In these days, in a satellite communication system or in a mobile communication system, error correction encoding techniques having a high encoding gain is being introduced in order to meet system requirements, such as low required power or reduction in the antenna size.
The low density parity check code has been known as an error correction code having an extremely high encoding gain, and hence an attempt is being made to introduce into the above mentioned communication systems of various configurations and storage unit such as magnetic recording.
The low density parity check code is not indicative simply of a single specified error correction code, but is a global appellation of error correction codes featured by a sparse check matrix, i.e., a matrix whose elements are mostly 0 and whose elements 1 are extremely few.
The low density parity check code is featured by the fact that, with its use, it is possible to construct an error correction encoding system having an extremely high encoding gain which is extremely close to the theoretical limit. This is made possible by the use of an iterative decoding system, such as sum-product, min-sum algorithm, etc., subject to selection of a sparse check matrix,
Among technical problems relevant to the decoding system of the low density parity check code, there is such a problem that larger numbers of random access memories (RAMs) are needed for retention of intermediate data temporarily generated in the course of the decoding processing.
In the decoding processing, the above intermediate data are iteratively updated. After a sufficient number of iterations, the transmission data are determined based on the plus or minus sign of data calculated from the intermediate data. The above processing of updating the intermediate data uses the same number of the intermediate data as the Hamming weight of the row vector of the check matrix, from one such row vector to another. Thus, for high-speed processing, it is necessary to refer to a larger number of data at the same time. It is thus necessary to use a larger number of random access memories (RAMs) and to segment the intermediate data in order for the RAMs to hold the segmented intermediate data.
In particular, in the low density parity check code of a high encoding rate, the Hamming weight of the row vector has a larger value, so that a correspondingly larger number of RAMs are required. On the other hand, the size of each RAM is determined by the check matrix of the code used and is not necessarily coincident with the size of the RAM provided by the apparatus on which the decoding device is implemented. Hence, there are also occasions where an increase in the number of RAMs leads to an increased storage capacity of the RAMs.
A conventional example technique relevant to the decoding device for the low density parity check code will now be described. (See Non-Patent Document 3). In the following, a matrix H is an r-row by n-column block matrix, where n is an integer not smaller than 1 and r is a positive integer smaller than n, as indicated by the following equation [Mathematical Expression 1] and each component of the matrix is a block matrix which is an m by m cyclic permutation matrix or a zero-matrix, where m is a positive integer.
                    H        =                  (                                                                      I                                      0                    ,                    0                                                                                                I                                      0                    ,                    1                                                                                                I                                      0                    ,                    2                                                                              …                                                              I                                      0                    ,                                          n                      -                      1                                                                                                                                            I                                      1                    ,                    0                                                                                                I                                      1                    ,                    1                                                                                                I                                      1                    ,                    2                                                                              …                                                              I                                      1                    ,                                          n                      -                      1                                                                                                                          ⋮                                            ⋮                                            ⋮                                                                                                                          ⋮                                                                    ⋮                                            ⋮                                            ⋮                                                                                                                          ⋮                                                                                      I                                                            r                      -                      1                                        ,                    0                                                                                                I                                                            r                      -                      1                                        ,                    1                                                                                                I                                                            r                      -                      1                                        ,                    2                                                                              …                                                              I                                                            r                      -                      1                                        ,                                          n                      -                      1                                                                                                    )                                    [                  Mathematical          ⁢                                          ⁢          Expression          ⁢                                          ⁢          1                ]            In the above equation [Mathematical Expression 1], Ii, j denotes an m by m cyclic permutation matrix or zero matrix, where i is an integer from 0 to r−1 and j is an integer from 0 to n−1. However, in the following description, Ii, j is taken to denote an m by m cyclic permutation matrix, for simplicity of explanation.
For a case in which, for a given component (i, j) in which Ii, j stands for a zero matrix, the basic operation is the same. The low density parity check code, which uses the matrix H of the equation [Mathematical Expression 1] as the check matrix, is specifically termed a quasi cyclic low density parity check code.
(a) and (b) of FIG. 7 each depict a block diagram of a decoding device of the conventional technique for the quasi cyclic low density parity check code. The decoding device includes a set of memories that hold the intermediate data, termed messages, generated in the course of the decoding processing. In addition, the decoding device includes a check node processing circuit for updating the messages, an addition unit and a delay circuit.
Data encoded in accordance with the quasi cyclic low density parity check code are sent over a communication channel and become inputs F0, F1, . . . , FN-1 of the decoding device, where N=mn. A bit sequence, indicating the plus or minus sign of the data held by the memories and updated, is output from the decoding device as being a result of decoding.
A method as well as a device for decoding by the conventional technique will now be described with reference to (a) and (b) of FIG. 7. It is observed that (b) of FIG. 7 is ones obtained by making the processing by the decoding device of (a) of FIG. 7 into a parallel processing, with the number of the parallel circuits being two. As a matter of the principle, the circuit shown in (b) of FIG. 7 is equivalent to that of (a) of FIG. 7. The following description will be made essentially with reference to (a) of FIG. 7.
Referring to (a) of FIG. 7, an m-number of data is stored in each of the memories (0), (1), . . . , (n−1), so that a total of mn data Z0, Z1, . . . , ZN-1 are stored. The initial values of the data Z0, Z1, . . . , ZN-1 are input data F0, F1, . . . , FN-1 to the decoding device, which input data are output data of the communication channel(s). These data are sequentially updated in the course of the processing for decoding which will now be described.
From the data Zu, where u is an integer from 0 to N−1, data Lu←v, as held by a memory (L) at the lower-most side of (a) of FIG. 7, where v is an integer from 0 to R−1, with R=mr, is subtracted, as indicated by the equation [Mathematical Expression 2] to yield data Zu→v.
[mathmatical Expression 2]Zu→v=Zu−Lu←v  [Mathematical Expression 2]The data Zu→v is delivered to a delay circuit as well as to a check node processing circuit, which the check node processing circuit performs the processing indicated by the equation [Mathematical Expression 3].
It is observed that, in the equation [Mathematical Expression 3], B(v) denotes a position in the check matrix where an element in a with row vector becomes 1, and that sgn(Z)=−1 if the value of Z is minus, and =+1 otherwise.
                              L                      u            ←            v                    ′                =                              ∏                                                            u                  ′                                ∈                                  B                  ⁡                                      (                    v                    )                                                                                                u                  ′                                ≠                u                                              ⁢                                    sgn              ⁡                              (                                  Z                                                            u                      ′                                        →                    v                                                  )                                      ⁢                                          min                                                                            u                      ′                                        ∈                                          B                      ⁡                                              (                        v                        )                                                                                                                        u                      ′                                        ≠                    u                                                              ⁢                                                                Z                                                            u                      ′                                        →                    v                                                                                                                          [                  Mathematical          ⁢                                          ⁢          Expression          ⁢                                          ⁢          3                ]            It is observed that L′u←v as calculated by the equation [Mathematical Expression 3] represents the result of update of the data Lu←v and is retained by the memory L at the lower most end of FIG. 7. It is the check node processing, indicated by the equation [Mathematical Expression 3], that performs the vital role in the processing for decoding of the low density parity check code.
Assume that Lv(1) and Lv(2) are the smallest and second smallest values in a set of the above data {|Zu→v∥uεB(v)}, respectively, and also assume that an element u of B(v) which will give Lv(1)=|Zu→v| is Umin. Also assume that, if Zu→v is of a negative value and otherwise, qu→v=1 and =0, respectively. In this case, the data L′u←v of the equation 3 [Mathematical Expression 3] may be expressed in accordance with the following equation [Mathematical Expression 4].
                              L                      u            ←            v                    ′                =                  {                                                                                                                (                                              -                        1                                            )                                                                                      s                        v                                            +                                              q                                                  u                          →                          v                                                                                                      ⁢                                      L                    v                                          (                      1                      )                                                                                                                    u                  ≠                                      u                    min                                                                                                                                                                  (                                              -                        1                                            )                                                                                      s                        v                                            +                                              q                                                  u                          →                          v                                                                                                      ⁢                                      L                    v                                          (                      2                      )                                                                                                                    u                  =                                      u                    min                                                                                                          [                  Mathematical          ⁢                                          ⁢          Equation          ⁢                                          ⁢          4                ]            Meanwhile, in the above Equation [Mathematical Expression 4], sv=ΣuεB(v)qu→v is set.
FIG. 8 depicts a block diagram showing an example formulation of a check node processing circuit 7-2 shown in FIG. 7. The data Zu→v is entered for all of elements u in the above set B(v). The data Zu→v is already quantized, with the uppermost bit specifying the sign (plus or minus) and with the remaining lower order bits specifying an absolute value.
The upper most bit and the lower order bits are separated from each other. The uppermost bit is delivered to a unit calculating the sign (plus or minus) in the equation [Mathematical Expression 4], whilst the lower order bits are entered to a unit calculating the smallest and second smallest values. The data L′u←v shown by the equation [Mathematical Expression 4] is thus obtained.
The above data L′u←v is added to the above mentioned data Zu→v as obtained through a delay circuit 7-4 of FIG. 7, as indicated by the equation [Mathematical Expression 5] and the result Zu of addition is retained at the same location in the above memory 7-1 of FIG. 7.
[Mathmatical Expression 5]Zu=Zu-v+L′u←v  [Mathematical Expression 5]The above described processing is carried out in the sequence of v=0, 1, . . . , R−1, whereby data in the memory is updated.
The foregoing represents a single decoding processing operation in the iterative decoding. The variable v specifies a with row vector of the check matrix, as described above. By carrying out the processing for the total of the row vectors, one round of decoding processing may come to a close. If, after iterating a sufficient number of the decoding processing operations, the value of Zu is negative, the result of the decoding of the received data Fn is set to 1 and, if otherwise, the result of the decoding is set to 0. The processing for decoding then comes to a close.
Thus, in the processing of decoding the low density parity check code, described above, it is necessary to provide a memory for storage of the data Zu, as the estimated information of the transmission bit sequence, and another memory for storage of the data Lu→v, which corresponds to the update hysteresis of the data Zu, as the estimated information of the transmission bit sequence.
For enabling efficient decoding, it is necessary to provide data Zu for all of the elements u of the set B(v), from one v (=0, 1, . . . , R−1) to another, and to deliver the data to the check node processing circuit.
It is thus necessary to access the memory a number of times equal to the number of the elements of B(v) to provide inputs to the check node processing circuit, if the data Zu are retained at the addresses of a single memory, for example. There are thus raised problems such as time lag until starting the calculations of the equations ([Mathematical Expression 4] or [Mathematical Expression 3]) as well as increased complexity in address generation.
On the other hand, if the data Zu are retained not in the single memory but at the same address of a plurality of segmented memories, the above mentioned problem of the time lag may be overcome. In the case of the quasi cyclic low density parity check code having the check matrix of the equation [Mathematical Expression 1], n-number of memories are provided, and data Zjm+k is retained at a kth address of a memory (j), where j denotes an integer from 0 to n−1 and k denotes an integer from 0 to m−1, as shown in (a) of FIG. 7. In this case, it is possible to provide data necessary for delivery to the check node processing circuit by accessing each memory only once. However, a problem then arises that a large number of memories need to be used.
In connection with reduction in the number of random-accessible memories, there is known a method in which the memory (L) at the lower end of FIG. 7 representing the conventional technique is dispensed with and the subtraction of the data Lu←v in the equation [Mathematical Expression 2] is omitted. See Non-Patent Document 4.
The formulation of a decoding device by this technique is shown in FIG. 9. The formulation is truly effective in reducing the circuit size. However, it is still necessary to use a larger number of RAMs for storing data Zu. In addition, since the subtraction of the data Lu←v is not carried out, bit errors are left over in an output of the processing device, thus offering a problem such as possible occurrence of deteriorating in the decoding characteristic.
There is also known a solution in which larger numbers of shift registers are used to avoid the use of RAMs to provide a formulation that is simple in structure and that lends itself to a high-speed operation. See, for example, the Patent Document 1. The formulation is, however, beset with a problem that the circuit size is increased in case the code length N is on the order of thousands of bits or more or in case there are many redundant bits and hence the coding rate is extremely low.    [Patent Document 1] JP Patent Kokai Publication No. JP-P2007-89064A    [Non-Patent Document 1] “Low Density Parity-Check Codes”, Robert Gallager, published by IEEE Transactions on Information Theory pp. 21 to 28, January 1962    [Non-Patent Document 2] “Good Error Correcting Codes Based on Very Sparse Matrices”, D. J. C. Mackay, published by IEEE Transactions on Information Theory, pp. 399-431, March 1999    [Non-Patent Document 3] “Efficient Serial Message-Passing Schedule for LDPC Decoding”, Eran Sharon, Simon Litsyn and Jacob Goldberger, published by IEEE Transactions on Information Theory, pp. 4076-4091, November 2007    [Non-Patent Document 4] “High Throughput Low-Density Parity-Check Decoder Architecture”, E. Yeo, P. Pakzad, B. Nikolic and V. Anantharam, 2001, published by IEEE Global Telecommunications Conference, pp. 3019-3024, November 2001